package com.breeze.leetcode.interview;

/**
 * https://leetcode-cn.com/problems/three-steps-problem-lcci/
 * 面试题 08.01. 三步问题
 * 三步问题。有个小孩正在上楼梯，楼梯有n阶台阶，小孩一次可以上1阶、2阶或3阶。实现一种方法，计算小孩有多少种上楼梯的方式。结果可能很大，你需要对结果模1000000007。
 * <p>
 * 解题：动态规划
 * 1. 最优子结构   F(n) = F(n-1) + F(n-2) + F(n-3)   等式后的即为最优子结构，且满足无后效性，因为F(n)的取值与F(n-1) .. 等具体是怎么取值并没有关系
 * 2. 状态转移方程 F(n) = F(n-1) + F(n-2) + F(n-3)
 * 3. 边界条件 F(1) = 1; F(2) = 2; F(3) = 4
 */
public class Solution0801 {
    /**
     * 动态规划1
     * <p>
     * 时间复杂度：O(n)
     * 空间复杂度：O(n)
     */
    public int waysToStep(int n) {
        if (n == 1) return 1;
        if (n == 2) return 2;
        if (n == 3) return 4;
        int[] dp = new int[n];
        dp[0] = 1;
        dp[1] = 2;
        dp[2] = 4;
        int mod = 1000000007;
        for (int i = 3; i < n; i++) {
            // 注意模的使用，防止数据溢出变为负数
            dp[i] = ((dp[i - 1] + dp[i - 2]) % mod + dp[i - 3]) % mod;
        }
        return dp[n - 1];
    }

    /**
     * 动态规划2 优化版
     * 时间复杂度：O(n)
     * 空间复杂度：O(1)
     */
    public int waysToStep1(int n) {
        if (n == 1) return 1;
        if (n == 2) return 2;
        if (n == 3) return 4;

        int a = 1, b = 2, c = 4;
        int mod = 1000000007;
        for (int i = 3; i < n; i++) {
            int temp = ((a + b) % mod + c) % mod;
            a = b;
            b = c;
            c = temp;
        }
        return c;
    }


    /**
     * 矩阵快速幂
     * TODO: 待学习
     */
    final static int mod = 1000000007;

    public int waysToStep2(int n) {
        //f = [1, 2, 4]
        long[] f = new long[]{1, 2, 4};

        if (n <= 3) {
            return (int) f[n - 1];
        }

        long[][] A = {{0, 0, 1}, {1, 0, 1}, {0, 1, 1}};
        long[][] B = matPow(A, n - 3);

        long res = 0;
        for (int i = 0; i < 3; i++) {
            res = (res + f[i] * B[i][2]) % mod;
        }

        return (int) res;
    }

    private long[][] matPow(long[][] A, int n) {
        // m = A.shape[0]
        int m = A.length;

        //B = np.eye(m, dtype=np.int64)
        long[][] B = new long[m][m];
        for (int i = 0; i < B.length; i++) {
            B[i][i] = 1;
        }

        while (n > 0) {
            if ((n & 1) != 0) {
                B = matMul(B, A);
            }
            A = matMul(A, A);
            n >>= 1;
        }
        return B;
    }

    private long[][] matMul(long[][] mat1, long[][] mat2) {
        int row1 = mat1.length;
        int row2 = mat2.length, column2 = mat2[0].length;

        long[][] resultMatrix = new long[row1][column2];
        for (int i = 0; i < row1; i++) {
            for (int j = 0; j < column2; j++) {
                for (int k = 0; k < row2; k++) {
                    resultMatrix[i][j] = (resultMatrix[i][j] + mat1[i][k] * mat2[k][j]) % mod;
                }
            }
        }
        return resultMatrix;
    }
}
